package Leetcode第一期;

import sun.misc.LRUCache;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : K k
 * @date : 12:49 2020/9/16
 */
public class LRU缓存机制_146  {
    //分为两个部分：hashmap 和 双向链表
    class DLinkedNode{
        //双向链表
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int key,int value){
            this.key=key;
            this.value=value;
        }
    }

    //HashMap
    private Map<Integer,DLinkedNode> cache=new HashMap<>();
    private int size; //量表长度
    private int capacity; //缓存容量
    DLinkedNode head,tail; //头尾结点

    public LRU缓存机制_146(int capacity) {
        this.size=0;
        this.capacity=capacity;
        this.head=new DLinkedNode();
        this.tail=new DLinkedNode();
        head.next=tail;
        tail.pre=head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node==null){
            //若不存在该节点
            return -1;
        }
        //若存在
        moveToHead(node);//移动到头
        return node.value;
    }

    public void put(int key, int value) {
        //put 需要放进两个地方
        DLinkedNode node = cache.get(key);
        if (node==null){
            //若不存在，则创建一个新结点
            DLinkedNode newNode = new DLinkedNode(key, value);
            //添加到hashmap
            cache.put(key,newNode);
            //添加到头部
            addToHead(newNode);
            ++size; //容量加1
            if (size>capacity){
                //若超过了容量，则将尾结点（最近最久未使用）去除
                //由于新节点以及最近使用的节点肯定是排在链表前面的所以位于最后的肯定是最久未使用
                DLinkedNode removeNode=removeTail();
                //从缓存中删除
                cache.remove(removeNode.key);
                --size;
            }
        }else {
            //若存在 覆盖value
            node.value=value;
            moveToHead(node);
        }
    }

    private DLinkedNode removeTail() {
        DLinkedNode node = tail.pre;
        node.pre.next=tail;
        tail.pre=node.pre;
        node.pre=null;
        node.next=null;
        return node;
    }

    private void addToHead(DLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private void moveToHead(DLinkedNode node) {
        if (node.pre==head){return;}
        if (size>1) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }
    }


    public static void main(String[] args) {
        LRU缓存机制_146 cache = new LRU缓存机制_146( 2 /* 缓存容量 */ );
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回  1
        cache.put(3, 3);    // 该操作会使得关键字 2 作废
        cache.get(2);       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得关键字 1 作废
        cache.get(1);       // 返回 -1 (未找到)
        cache.get(3);       // 返回  3
        cache.get(4);       // 返回  4

    }



}
